/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/fibonacci
   @Language: C++
   @Datetime: 16-02-09 04:39
   */

class Solution{
public:
	/**
	 * @param n: an integer
	 * @return an integer f(n)
	 * Tip : 0, 1, 1, 2, 3, 5, ...
	 */
	int fibonacci(int n) {
		// write your code here
		int p=0, f=1;
		if (n<2) return n-1;
		for(n-=2; n--; f+=p, p=f-p);
		return f;
	}
};
